// 调整堆
const HeapAdjust = function (arr, s, m) { //假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆 
    const rc = arr[s];
    for (j = 2 * s; j <= m; j *= 2) //沿key较大的孩子结点向下筛选 
    {
        if (j < m && arr[j] < arr[j + 1]) j++; //j为key较大的记录的下标 
        if (rc >= arr[j]) break; //rc应插入在位置s上 
        arr[s] = arr[j];
        s = j;
    }
    arr[s] = rc; //插入 
}

// 建初堆
const CreatHeap = function (arr) { //把无序序列arr[0..n]建成大根堆
    const n = arr.length - 1;
    // 反复调用HeapAdjust
    // 只需对非叶子节点进行调节即可
    for (i = Math.floor(n / 2); i >= 0; i--) {
        HeapAdjust(arr, i, n);
    }
}

// 堆排序算法的实现
const HeapSort = function (arr) { //对顺序表arr进行堆排序
    CreatHeap(arr); //把无序序列arr[0..arr.length]建成大根堆
    for (i = arr.length - 1; i >= 0; i--) {
        //将堆顶记录和当前未经排序子序列arr[0..i]中最后一个记录互换
        [arr[0], arr[i]] = [arr[i], arr[0]];
        HeapAdjust(arr, 0, i - 1); //将arr[0..i-1]重新调整为大根堆
    }
}

const arr = [49, 38, 65, 97, 76, 13, 27, 49]

HeapSort(arr)

console.log(arr)